#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<math.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

TreeNode* CreateTree()
{
	TreeNode* node1 = BuyTreeNode(1);
	TreeNode* node2 = BuyTreeNode(2);
	TreeNode* node3 = BuyTreeNode(3);
	TreeNode* node4 = BuyTreeNode(4);
	TreeNode* node5 = BuyTreeNode(5);
	TreeNode* node6 = BuyTreeNode(6);
	TreeNode* node7 = BuyTreeNode(7);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node5->right = node7;

	return node1;
}

void PrevOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void BackOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BackOrder(root->left);
	BackOrder(root->right);
	printf("%d ", root->data);

}

int TreeSize(TreeNode* root)
{
	return root == NULL ? 0 : 
		TreeSize(root->left) + 
		TreeSize(root->right) + 1;
}

int TreeHeight(TreeNode* root)
{
	if (root == NULL)
		return 0;
	return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}

int TreeLevelK(TreeNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeLevelK(root->left, k - 1) + 
		TreeLevelK(root->right, k - 1);
}
int main()
{
	TreeNode* root = CreateTree();

	PrevOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	BackOrder(root);
	printf("\n");

	int size = TreeSize(root);
	printf("TreeSize: %d\n", size);
	int height = TreeHeight(root);
	printf("TreeHeight: %d\n", height);

	int k = 4;
	int n = TreeLevelK(root, k);
	printf("TreeLevelK: %d\n", n);

	return 0;
}